package capricornus.scene.controller
{
	public class ActionSceneDataSearcher {
		private var _closeListData:Array;
		private var _map:Array;
		private var _openList:Array;
		private var _openListData:Array;
		private var _currentColumn:int;
		private var _currentRow:int;
		private var _keyConst:int;
		private var _totalRows:int;
		private var _totalColumns:int;
		private var _parentColumn:int;
		private var _startColumn:int;
		private var _parentRow:int;
		private var _startRow:int;
		private var _maxStep:int;
		private var _parentG:Number;
		private var _unCrossNumber:Number;
		private var _closeMap:Object;
		private var _openMap:Object;
		
		private var temp:int;
		public function ActionSceneDataSearcher(map:Array, totalRows:int, totalColumns:int, unCrossNumber:Number, maxStep:int=10000):void {
			_map = map;
			_unCrossNumber = unCrossNumber;
			_keyConst = Math.pow(10, totalColumns.toString().length);
			//_mutiple = Math.pow(10, normalNumber.toString().length-1);
			_totalRows = totalRows;
			_totalColumns = totalColumns;
			_maxStep = maxStep;
		}
		public function clear():void {
			_map = null;
		}
		public function search(startRow:uint, startColumn:uint, endRow:uint, endColumn:uint):Array {
			_startRow = startRow;
			_startColumn = startColumn;
			_parentG = 0;
			_parentRow = _startRow;
			_parentColumn = _startColumn;
			//_closeList = [];
			_closeListData = [];
			_closeMap = [];
			_openList = [];
			_openListData = [];
			_openMap = [];
			var step:int = 0;
			while (step<_maxStep) {
				//_closeList.push(_closeListData.length);
				_closeMap[_startRow*_keyConst+_startColumn] = _closeListData.length;
				_closeListData.push(_startRow, _startColumn, _parentRow, _parentColumn);
				if (_startRow == endRow && _startColumn == endColumn) {
					break;
				}
				step++;
				var maxRows:int = _startRow+1;
				for (var row:int = _startRow-1; row<=maxRows; row++) {
					if (row<0 || row>_totalRows) continue;
					_currentRow = row;
					var sameRow:Boolean = row == _startRow;
					var k:int = _currentRow*_totalColumns;
					var maxColumns:int = _startColumn+1;
					for (var column:int = _startColumn-1; column<=maxColumns; column++) {
						if (column<0 || column>_totalColumns || (sameRow && column == _startColumn)) continue;
						_currentColumn = column;
						var currentNumber:int = _map[k+column];
						if (_unCrossNumber == currentNumber || _closeMap[_currentRow*_keyConst+column] != null) {
							continue;
						}
						if (_currentRow+1 == _startRow) {
							if (_currentColumn+1 == _startColumn) {
								if (_map[_currentRow*_totalColumns+_startColumn] == _unCrossNumber || _map[_startRow*_totalColumns+_currentColumn] == _unCrossNumber) {
									continue;
								}
							} else if (_currentColumn-1 == _startColumn) {
								if (_map[_currentRow*_totalColumns+_startColumn] == _unCrossNumber || _map[_startRow*_totalColumns+_currentColumn] == _unCrossNumber) {
									continue;
								}
							}
						} else if (_currentRow-1 == _startRow) {
							if (_currentColumn+1 == _startColumn) {
								if (_map[_currentRow*_totalColumns+_startColumn] == _unCrossNumber || _map[_startRow*_totalColumns+_currentColumn] == _unCrossNumber) {
									continue;
								}
							} else if (_currentColumn-1 == _startColumn) {
								if (_map[_currentRow*_totalColumns+_startColumn] == _unCrossNumber || _map[_startRow*_totalColumns+_currentColumn] == _unCrossNumber) {
									continue;
								}
							}
						}
						var g:Number = 1;
						var h:Number = ((endRow>_currentRow ? endRow-_currentRow : _currentRow-endRow)+(endColumn>_currentColumn ? endColumn-_currentColumn : _currentColumn-endColumn));//*_mutiple;
						//addNodeToOpenList
						var length:int = _openList.length;
						var parentIndex:int;
						var parent:int;
						var f:Number = g+h;
						var dataIndex:int;
						var key:uint = _currentRow*_keyConst+_currentColumn;
						if (_openMap[key] == null) {
							dataIndex = _openListData.length;
							_openListData.push(_currentRow, _currentColumn, g, f, _startRow, _startColumn);
							_openMap[_currentRow*_keyConst+_currentColumn] = dataIndex;
							_openList.push(dataIndex);
							length++;
							while (true) {
								parentIndex = length/2;
								if (parentIndex<1) break;
								parent = _openList[parentIndex-1];
								if (_openListData[parent+3]>f) {
									_openList[length-1] = parent;
									_openList[parentIndex-1] = dataIndex;
									length = parentIndex;
								} else {
									break;
								}
							}
						} else {
							dataIndex = _openMap[key];
							var i:int = _openList.indexOf(dataIndex);
							g += _parentG;
							if (g<_openListData[dataIndex+2]) {
								_openListData[dataIndex+2] = g;
								_openListData[dataIndex+3] = f;
								_openListData[dataIndex+4] = _startRow;
								_openListData[dataIndex+5] = _startColumn;
								index = i+1;
								while (true) {
									parentIndex = index/2;
									if (parentIndex<1) break;
									parent = _openList[parentIndex-1];
									if (_openListData[parent+3]>f) {
										_openList[index-1] = parent;
										_openList[parentIndex-1] = dataIndex;
										index = parentIndex;
									} else {
										break;
									}
								}
							}
						}
						//
					}
				}
				//temp++;//17875
				if (_openList.length == 0) {
					_clearData();
					return null;
				}
				var index:int = _openList.shift();
				_startRow = _openListData[index];
				_startColumn = _openListData[index+1];
				_parentG = _openListData[index+2];
				_parentRow = _openListData[index+4];
				_parentColumn = _openListData[index+5];
				delete _openMap[_startRow*_keyConst+_startColumn];
			}
			if (step>=_maxStep) {
//				Main.print('search path over step');
				return null;
			}
			return _formatPath(endRow*_keyConst+endColumn);
		}
		private function _clearData():void {
			//_closeList = null;
			_closeListData = null;
			_closeMap = null;
			_openList = null;
			_openListData = null;
			_openMap = null;
		}
		private function _formatPath(endKey:uint):Array {
			var index:int = _closeMap[endKey];
			_parentRow = _closeListData[index+2];
			_parentColumn = _closeListData[index+3];
			var pathList:Array = [_closeListData[index], _closeListData[index+1]];
			while (true) {
				index = _closeMap[_parentRow*_keyConst+_parentColumn];
				_parentRow = _closeListData[index+2];
				_parentColumn = _closeListData[index+3];
				pathList.unshift(_closeListData[index], _closeListData[index+1]);
				if (index == 0) break;
			}
			_clearData();
			return pathList;
		}
	}
}